package com.saprk.demoarithmetic.arithmetic;

import java.util.Arrays;
import java.util.Objects;

/**
 * @author fuqiang
 * @Description
 * @Date 2021-04-12
 */
public class FastSort {
    /**
     * 快速排序
     * @param arr
     * @return
     */
    public static void fastSort(int[] arr){
        if(Objects.isNull(arr)){
            return;
        }
        if(1 >= arr.length){
            return ;
        }
        sort(arr, 0, arr.length-1);
    }

    public static void sort(int[] arr,int left,int right){

        if( left > right){
            return ;
        }
        int i = left,j = right;
        int base = arr[left];
        while( i < j) {
            // 从后面循环起
            while ( arr[j] <= base && i < j){
                j--;
            }
            // 从后面循环起
            while( arr[i] >= base && i < j){
                i++;
            }
            if(i < j){
                int temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
            }
        }
        // 基数归位
        arr[left] = arr[i];
        arr[i] = base;
        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,12,3,44,133,421,32};
//        fastSort(arr);
        Arrays.sort(arr);
    }
}
